package leetcode.editor.template.sort;

// 归并模板
public class Merge {
    // 直接申请一个临时数组变量
    private int[] temp;

    public int[] sortArray(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void sort(int[] nums, int l, int r) {
        // 单个元素不用排序
        if (l == r) {
            return;
        }

        int m = l + (r - l) / 2;
        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, l, m);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, m + 1, r);

        // 将两部分有序数组合并成一个有序数组
        merge(nums, l, m, r);
    }

    public void merge(int[] nums, int l, int m, int r) {
        for (int i = l; i <= r; i++) {
            temp[i] = nums[i];
        }

        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            if (j == r + 1) {
                nums[k] = temp[i++];
            } else if (i == m + 1) {
                nums[k] = temp[j++];
            } else if (temp[j] < temp[i]) {
                nums[k] = temp[j++];
            } else {
                nums[k] = temp[i++];
            }
        }
    }
}
